package cn.cnsuh.q47_permuteUnique;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0) return res;
        List<Integer> list = new ArrayList<>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,res,0,list);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, int i, List<Integer> list) {
        if(i == nums.length){
            res.add(new ArrayList<>(list));
        }
        for (int j = 0; j < nums.length; j++) {
            if(vis[j]||(j>0&&nums[j]==nums[j-1]&&!vis[j-1])){
                continue;
            }
            list.add(nums[j]);
            vis[j] = true;
            dfs(nums,res,i+1,list);
            vis[j] = false;
            list.remove(i);
        }
    }
}
